package gold.contest;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC5253 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        Map<String, String> memo = new HashMap<>();

        public long[] kthPalindrome(int[] queries, int intLength) {
            long[] ans = new long[queries.length];
            for (int i = 0; i < queries.length; i++) {
                ans[i] = Long.parseLong(getKthPalindrome(intLength, queries[i], false));
            }
            return ans;
        }

        public String getKthPalindrome(int intLength, int k, boolean isInner) {
            long innerEachBitCnt = (long) (Math.pow(10, (int) ((intLength - 1) / 2)));
            if (!isInner && k > innerEachBitCnt * 9) return "-1";
            if (intLength <= 0) return "";
            if (intLength == 1) return isInner ? String.valueOf(k - 1) : String.valueOf(k);

            String key = intLength + "_" + k;
            if (memo.containsKey(key)) return memo.get(key);

            // 先确定 以哪个数字开头
            StringBuilder startBit = new StringBuilder(String.valueOf((int) ((k - 1) / innerEachBitCnt) + (isInner ? 0 : 1)));
            String middlePart = getKthPalindrome(intLength - 2, (int) ((k - 1) % innerEachBitCnt + 1), true);

            startBit.append(middlePart + startBit.toString());
            memo.put(key, startBit.toString());
            return startBit.toString();
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.getKthPalindrome(3, 90, false));
        System.out.println(solution.getKthPalindrome(5, 9, false));
        System.out.println(solution.getKthPalindrome(4, 41, false));

//        System.out.println(solution.getKthPalindrome(3, 88));
        System.out.println(Arrays.toString(solution.kthPalindrome(InputUtil.toIntegerArray("[1,2,3,4,5,90]"), 3)));
        System.out.println(Arrays.toString(solution.kthPalindrome(InputUtil.toIntegerArray("[2,4,6]"), 4)));
        System.out.println(Arrays.toString(solution.kthPalindrome(InputUtil.toIntegerArray("[2,201429812,8,520498110,492711727,339882032,462074369,9,7,6]"), 1)));
        System.out.println(Arrays.toString(solution.kthPalindrome(InputUtil.toIntegerArray("[449229674,501930675,40059525,908875541,9,672504016]"), 5)));
    }

    public static void main(String[] args) throws Exception {
        LC5253 an = new LC5253();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
